/*
Date:20210423 21:46pm
key:G(i)表示i个不同元素组成的可能个数,注意G(0)是一种可能
    G(i)=G(0)*G(i-1)+G(1)*G(i-2)```G(i-1)
    相当于左子树由0个元素变化到i-1，右则相反。其中每一刻可能都是左子树可能乘右子树可能。

*/
class Solution {
public:

    int numTrees(int n) 
    {
        if(n==0){return 0;}
        if(n==1){return 1;}

        int*dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<n+1;i++)
        {
            cout<<i;
            dp[i]=0;
            for(int j=1;j<i+1;j++)
            {
                dp[i]+=dp[j-1]*dp[i-j];
            }
            
        }


        return dp[n];
    }
};